Programmable logic devices (“PLDs”) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (“FPGA”), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (“IOBs”), configurable logic blocks (“CLBs”), dedicated random access memory blocks (“BRAMs”), multipliers, digital signal processing blocks (“DSPs”), processors, clock managers, delay lock loops (“DLLs”), and so forth. Notably, as used herein, “include” and “including” mean including without limitation. One such FPGA is the Xilinx Virtex-II FPGA available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124.
Another type of PLD is the Complex Programmable Logic Device (“CPLD”). A CPLD includes two or more “function blocks” connected together and to input/output (“I/O”) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (“PLAs”) and Programmable Array Logic (“PAL”) devices. Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, for example, using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable.
For purposes of clarity, FPGAs are described below though other types of PLDs may be used. FPGAs may include one or more embedded microprocessors. For example, a microprocessor may be located in an area reserved for it, generally referred to as a “processor block.”
FPGAs have more recently been used in digital signal processing applications. Heretofore, implementing Fast Fourier Transform (“FFT”) processors in FPGAs has been problematic for large point-size applications. Examples of such applications include demanding communications applications and Synthetic Aperture Radar (“SAR”) applications, among other known FFT uses.
More particularly, applications involving high precision, conventionally 20 or more bits, and high resolution, conventionally 16,384 or more samples (“point size”), had significant phase factor memory consumption issues. To alleviate these issues, the phase-factor memories that were completely look-up table (“LUT”)-based were replaced by Direct Digital Synthesis (“DDS”) blocks. Each DDS contains a sub-sampled LUT, a phase accumulator and some correction circuitry, which combines the phase-factor samples and the phase-accumulator values. Because precision of the phase accumulator scales linearly, an increase in bit precision may be accommodated by increasing the width of the accumulator, namely increasing the width of the look-up table (“LUT”). However, the size of the LUT scales exponentially with each incremental increase in point size, namely the width of the phase, φ. Thus, still large memory usage resulted for a high resolution FFT processor.
Accordingly, it would be desirable and useful to have a high precision and high resolution FFT processor that may be implemented in an FPGA which overcomes one or more of the above mentioned limitations.